What is the time complexity of the following code snippet?int count = 0;for (int i = 1; i

Question

What is the time complexity of the following code snippet?
int count = 0;
for (int i = 1; i <= n; i *= 2) {
for (int j = 1; j <= i; j++) {
for (int k = 1; k <= n; k *= 2) {
count++;
}
}
}
cout << count;

a)
O(n)
b)
O(log n)
c)
O(n log n)
d)
O(n^2)

Correct answer is option 'D'. Can you explain this answer?

Answer

The outer loop runs log2(n) times, the middle loop runs i times, and the inner loop runs log2(n) times. Hence, the time complexity is O(n^2).

Answer

Understanding the Code Snippet
The given code snippet consists of three nested loops, which we will analyze to determine its time complexity.

Outer Loop Analysis
- The outer loop runs with `i` starting from 1 and doubling each iteration until `i` exceeds `n`.
- The iterations for `i` will be: 1, 2, 4, 8, ..., up to the largest power of 2 less than or equal to `n`.
- This results in approximately `log2(n)` iterations.

Middle Loop Analysis
- The middle loop iterates from `j = 1` to `i`.
- The number of iterations depends on the current value of `i`, which varies from 1 to `n`.
- In the worst case, when `i` is at its maximum value (i.e., `n`), the middle loop runs `n` times.

Inner Loop Analysis
- The inner loop runs with `k`, starting from 1 and doubling each iteration until it exceeds `n`.
- Similar to the outer loop, this loop also runs for approximately `log2(n)` iterations.

Combining the Complexity
- The total count of operations can be calculated as follows:
- For each value of `i`, we have:
- Middle loop executes `i` times.
- Inner loop executes `log2(n)` times.
- The total operations can be expressed as:
$$
Total = \sum_{i=1}^{n} (i \cdot log2(n))
$$
- The sum of `i` from 1 to `n` is $\frac{n(n+1)}{2}$, which simplifies to $O(n^2)$.

Final Complexity
- Thus, the overall time complexity of the entire code snippet is:
$$
O(n^2 \cdot log2(n)) = O(n^2)
$$
- Therefore, the correct answer is option **'D'**: O(n²).

Similar Software Development Doubts

What is the time complexity of the following code snippet?int count = 0;for (int i = 1; i <= n; i *= 2) { for (int j = 0; j < n; j++) { count++; }}cout << count;

What is the time complexity of the following code snippet?int count = 0;for (int i = 1; i <= n; i *= 2) { for (int j = 0; j < i; j++) { count++; }}cout << count;

What is the time complexity of the following code snippet?int count = 0;for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { count++; }}cout << count;

What is the time complexity of the following code snippet?int count = 0;for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j *= 2) { count++; }}cout << count;

What is the time complexity of the following code snippet?for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cout << i << " " << j << endl; }}

Top Courses for Software DevelopmentView all

How to become an Expert of MS Excel

ChatGPT for Everything: How to Use ChatGPT?

Basics of Python

Java Programming Basics

Python- Mastering Development in Python

Top Courses for Software Development

Top Courses for Software Development

Suggested Free Tests

Related Content

Schools

Competitive Examinations

Quick Access Links

Technical Exams